{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #黑白方格画"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: paintingPlan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #黑白方格画"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 `n * n` 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），所选行数、列数均可为 0。\n",
    "\n",
    "小扣希望最终的成品上需要有 `k` 个黑色格子，请返回小扣共有多少种涂色方案。\n",
    "\n",
    "注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`n = 2, k = 2`\n",
    ">\n",
    ">输出：`4`\n",
    "> \n",
    ">解释：一共有四种不同的方案：\n",
    ">第一种方案：涂第一列；\n",
    ">第二种方案：涂第二列；\n",
    ">第三种方案：涂第一行；\n",
    ">第四种方案：涂第二行。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`n = 2, k = 1`\n",
    "> \n",
    ">输出：`0`\n",
    "> \n",
    ">解释：不可行，因为第一次涂色至少会涂两个黑格。\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`n = 2, k = 4`\n",
    "> \n",
    ">输出：`1`\n",
    ">\n",
    ">解释：共有 2*2=4 个格子，仅有一种涂色方案。\n",
    "\n",
    "**限制：**\n",
    "- `1 <= n <= 6`\n",
    "- `0 <= k <= n * n`\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ccw6C7](https://leetcode.cn/problems/ccw6C7/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ccw6C7](https://leetcode.cn/problems/ccw6C7/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n2', '2\\n1', '2\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        假设有a行b列被涂色，则总涂色面积为 (a+b) * n - ab\n",
    "        则有方程 an + bn - ab = k\n",
    "        =>   n *n + an + bn - ab = n * n - k\n",
    "        (n-a)(n-b) = n*n - k\n",
    "        \"\"\"\n",
    "        if n * n == k or k == 0: return 1\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if (i + j) * n - i * j == k:\n",
    "                    ans += math.comb(n, i) * math.comb(n, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def C(self, n, m):\n",
    "      if m == 0 or n == m:\n",
    "        return 1\n",
    "      return self.C(n - 1, m - 1) + self.C(n - 1, m)\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      L = 0\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          key = i * n + j * n - i *j\n",
    "          if key == k:\n",
    "            L += self.C(n, i) * self.C(n, j)\n",
    "      if k == 0 or k == n * n:\n",
    "        return 1\n",
    "      return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "\n",
    "        # assume paint x row, y column, then the cell number is:\n",
    "        # n * (x + y) - x * y = k\n",
    "\n",
    "        if n * n == k:\n",
    "            return 1\n",
    "\n",
    "        ret = 0\n",
    "        for x in range(n + 1):\n",
    "            for y in range(n + 1):\n",
    "\n",
    "                if n * (x+y) - x * y == k:\n",
    "                    # print(x)\n",
    "                    # print(y)\n",
    "                    # print(comb(n, x))\n",
    "                    # print(comb(n, x))\n",
    "                    # print('-------------------')\n",
    "                    ret += comb(n, x) * comb(n, y)\n",
    "        \n",
    "        return ret\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == 0 or k == n * n : return 1\n",
    "        def comb(a: int, b: int) -> int:\n",
    "            t = 1\n",
    "            for i in range(b):\n",
    "                t = t * (a - i) // (i + 1)\n",
    "            return t\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n * (i + j) - (i * j) == k:\n",
    "                    ans += comb(n, i) * comb(n, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == n*n:\n",
    "            return 1\n",
    "        num = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if k == i * n + j * n - i *j:\n",
    "                    up = 1\n",
    "                    down = 1\n",
    "                    for m in range(i):\n",
    "                        up *= n-m\n",
    "                        down *= m+1\n",
    "\n",
    "                    up2 = 1\n",
    "                    down2 = 1\n",
    "                    for m in range(j):\n",
    "                        up2 *= n-m\n",
    "                        down2 *= m+1\n",
    "                    num += up* up2//down//down2\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res       \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def paintingPlan(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        plan = 0\n",
    "        if n**2 == k:  # 全涂的情况\n",
    "            return 1\n",
    "\n",
    "        def C(n, m):  # 排列组合公式  n!/(m!*(n-m)!)  其中！是阶乘\n",
    "            return int(math.factorial(n) / math.factorial(m) / math.factorial(n-m))\n",
    "\n",
    "        for i in range(n+1):\n",
    "            for j in range(n+1):\n",
    "                if (i*n + j*n - i*j) == k:    # 减去重复后的黑格子计算公式\n",
    "                    plan += C(n,i)*C(n,j)\n",
    "        return plan\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      def C(n, m):\n",
    "        if m == 0 or n == m:\n",
    "          return 1\n",
    "        return C(n - 1, m - 1) + C(n - 1, m)\n",
    "      L = 0\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if i * n + j * n - i *j == k:\n",
    "            L += C(n, i) * C(n, j)\n",
    "      if k in (0, n * n):\n",
    "        return 1\n",
    "      return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def zuhe(x,y):\n",
    "            a,b,c=1,1,1\n",
    "            for i in range(1,x+1):\n",
    "                a*=i\n",
    "            for j in range(1,y+1):\n",
    "                b*=j\n",
    "            for k in range(1,x-y+1):\n",
    "                c*=k\n",
    "            return a/(b*c)  \n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i+j)*n-i*j==k:\n",
    "                    res+=zuhe(n,i)*zuhe(n,j)\n",
    "                else:\n",
    "                    continue\n",
    "        return int(res)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in [0,n*n]:return 1\n",
    "        def get(n,k):\n",
    "            res = 1\n",
    "            for i in range(n,n-k,-1):\n",
    "                res*=i\n",
    "            for i in range(1,k+1):\n",
    "                res//=i\n",
    "            return res\n",
    "\n",
    "        ans  = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i+j)*n-i*j==k:\n",
    "                    ans += get(n,i)*get(n,j)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      if k==0 or k==n*n:\n",
    "        return 1\n",
    "      def mc(n,j):\n",
    "        if j == 0:\n",
    "          return 0\n",
    "        return math.comb(n,j)\n",
    "      se = set()\n",
    "      for i in range(n+1):\n",
    "        for j in range(i,n+1):\n",
    "          if (i+j)*n-i*j == k:\n",
    "            se.add((i,j),)\n",
    "      re = 0\n",
    "      for i,j in se:\n",
    "        if i == j:\n",
    "          re += mc(n,i)**2\n",
    "        else:\n",
    "          re += (math.comb(n,i) * math.comb(n,j))*2\n",
    "      return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res       \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        ans=0\n",
    "        trys=[]\n",
    "        if k==n**2:\n",
    "            return 1\n",
    "        for lit in range(2**n):\n",
    "            trys+=[list(map(int,bin(lit)[2:].zfill(n)))]\n",
    "        for try1 in trys:\n",
    "            for try2 in trys:\n",
    "                a=sum(try1)\n",
    "                b=sum(try2)\n",
    "                if k==n*(a+b)-a*b:\n",
    "                    ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        def C(n,a)-> int:\n",
    "            res=1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res\n",
    "        if k==0 or k==n*n:\n",
    "            return 1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j)==k:\n",
    "                    ans+=C(n,i)*C(n,j)\n",
    "        return int(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        import math\n",
    "        #遍历合适的行数和列数\n",
    "        count=0\n",
    "        for i in range(k//n+1):\n",
    "            for j in range(k//n+1):\n",
    "                #行和列满足以下关系\n",
    "                if i*j == n*(i+j)-k:\n",
    "                    if j==n:\n",
    "                        return 1\n",
    "                    count+=comb(n,i)*comb(n,j)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        假设有a行b列被涂色，则总涂色面积为 (a+b) * n - ab\n",
    "        则有方程 an + bn - ab = k\n",
    "        =>   n *n + an + bn - ab = n * n - k\n",
    "        (n-a)(n-b) = n*n - k\n",
    "        \"\"\"\n",
    "        if n * n == k or k == 0: return 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i + j) * n - i * j == k:\n",
    "                    ans += math.comb(n, i) * math.comb(n, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == n ** 2 or k == 0:\n",
    "            return 1\n",
    "        elif k < n:\n",
    "            return 0\n",
    "# n(i + j) - i * j = k\n",
    "# j = (k - n * i) / (n - i)\n",
    "        answer = 0\n",
    "        for row in range(n):\n",
    "            if k - n * row < 0:\n",
    "                break \n",
    "            if (k - n * row) % (n - row) == 0:\n",
    "                column = (k - n * row) // (n - row)\n",
    "                answer += math.comb(n, row) * math.comb(n, column)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if n * n == k or k == 0: return 1\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if (i + j) * n - i * j == k:\n",
    "                    ans += math.comb(n, i) * math.comb(n, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            if k == 0 or k == 4:\n",
    "                return 1\n",
    "            elif k == 2 or k == 3:\n",
    "                return 4\n",
    "            else:\n",
    "                return 0\n",
    "        if n == 3:\n",
    "            if k == 0 or k == 9:\n",
    "                return 1\n",
    "            elif k == 5 or k == 8:\n",
    "                return 9\n",
    "            elif k == 3 or k == 6:\n",
    "                return 6\n",
    "            elif k == 7:\n",
    "                return 18\n",
    "            else:\n",
    "                return 0\n",
    "        if n == 4:\n",
    "            if k == 0 or k == 16:\n",
    "                return 1\n",
    "            elif k == 4:\n",
    "                return 8\n",
    "            elif k == 8:\n",
    "                return 12\n",
    "            elif k == 7 or k == 15:\n",
    "                return 16\n",
    "            elif k == 10 or k == 14:\n",
    "                return 48\n",
    "            elif k == 13:\n",
    "                return 32\n",
    "            elif k == 12:\n",
    "                return 44\n",
    "            else:\n",
    "                return 0\n",
    "        if n == 5:\n",
    "            if k == 0 or k == 25:\n",
    "                return 1\n",
    "            elif k == 5:\n",
    "                return 10\n",
    "            elif k == 9 or k ==24:\n",
    "                return 25\n",
    "            elif k == 10 or k == 15:\n",
    "                return 20\n",
    "            elif k == 13 or k == 22 or k ==23:\n",
    "                return 100\n",
    "            elif k == 21:\n",
    "                return 150\n",
    "            elif k == 20:\n",
    "                return 10\n",
    "            elif k == 19:\n",
    "                return 200\n",
    "            else:\n",
    "                return 0\n",
    "        if n == 6:\n",
    "            if k == 0 or k == 36:\n",
    "                return 1\n",
    "            elif k == 6:\n",
    "                return 12\n",
    "            elif k == 12:\n",
    "                return 30\n",
    "            elif k == 11 or k == 35:\n",
    "                return 36\n",
    "            elif k == 18:\n",
    "                return 40\n",
    "            elif k == 16:\n",
    "                return 200\n",
    "            elif k == 24:\n",
    "                return 630\n",
    "            elif k == 21 or k == 33:\n",
    "                return 240\n",
    "            elif k == 20:\n",
    "                return 225\n",
    "            elif k == 30:\n",
    "                return 612\n",
    "            elif k == 26 or k == 34:\n",
    "                return 180\n",
    "            elif k == 31:\n",
    "                return 72\n",
    "            elif k == 28:\n",
    "                return 450\n",
    "            elif k == 27:\n",
    "                return 400\n",
    "            elif k == 32:\n",
    "                return 405\n",
    "            else:\n",
    "                return 0\n",
    "            \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        import math\n",
    "        count=0\n",
    "        for i in range(k//n+1):\n",
    "            for j in range(k//n+1):\n",
    "                if i*j == n*(i+j)-k:\n",
    "                    if (i==n or j==n) and i+j !=n:\n",
    "                        continue\n",
    "                    if j==n:\n",
    "                        return 1\n",
    "                    count+=comb(n,i)*comb(n,j)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        假设有a行b列被涂色，则总涂色面积为 (a+b) * n - ab\n",
    "        则有方程 an + bn - ab = k\n",
    "        =>   n *n + an + bn - ab = n * n - k\n",
    "        (n-a)(n-b) = n*n - k\n",
    "        \"\"\"\n",
    "        if n * n == k or k == 0: return 1\n",
    "        def C(x, y):\n",
    "            return int(factorial(x) / (factorial(y) * factorial(x - y)))\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if (i + j) * n - i * j == k:\n",
    "                    ans += C(n, i) * C(n, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res       \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def C(self, n, m):\n",
    "      if m == 0 or n == m:\n",
    "        return 1\n",
    "      return self.C(n - 1, m - 1) + self.C(n - 1, m)\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      L = 0\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if i * n + j * n - i *j == k:\n",
    "            L += self.C(n, i) * self.C(n, j)\n",
    "      if k == 0 or k == n * n:\n",
    "        return 1\n",
    "      return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0, n * n): return 1\n",
    "        \n",
    "        def get(n,a):\n",
    "            #计算组合公式递归版\n",
    "            def helper(n):\n",
    "                if n <= 1:return 1\n",
    "                return  n * helper(n-1)\n",
    "            return helper(n) / (helper(a) * helper(n - a)) \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n * (i + j) - (i * j) == k:\n",
    "                    ans += get(n, i) * get(n, j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        ans=0\n",
    "        import math\n",
    "        if k<n and k>0:\n",
    "            return 0\n",
    "        if k==n**2 or k==0:\n",
    "            return 1\n",
    "        \n",
    "        def get(x,y):\n",
    "            return math.comb(n,x)*math.comb(n,y)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j)==k:\n",
    "                    ans+=get(i,j)\n",
    "        return int(ans)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def C(self, n, m):\n",
    "      if m == 0 or n == m:\n",
    "        return 1\n",
    "      return self.C(n - 1, m - 1) + self.C(n - 1, m)\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      L = 0\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if i * n + j * n - i *j == k:\n",
    "            L += self.C(n, i) * self.C(n, j)\n",
    "      if k in (0, n * n):\n",
    "        return 1\n",
    "      return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        c = [0] * (n + 1)\n",
    "        c[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            c[i] = c[i - 1] * (n - i + 1) // i\n",
    "        if k == 0 or k == n * n:\n",
    "            return 1\n",
    "        num_ways = 0\n",
    "        for num_rows in range(n + 1):\n",
    "            for num_cols in range(n + 1):\n",
    "                if n * (num_rows + num_cols) - num_rows * num_cols == k:\n",
    "                    num_ways += c[num_rows] * c[num_cols]\n",
    "        return num_ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res       \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        def combinationNum(n, m): # 计算组合数公式 C(n, m) = n! / (m! * (n - m)!)\n",
    "            res = 1\n",
    "            for i in range(n, n - m, -1):\n",
    "                res *= i\n",
    "            for j in range(1, m + 1):\n",
    "                res /= j\n",
    "            return int(res)\n",
    "\n",
    "        if k == 0 or k == n * n:\n",
    "            return 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n + 1): # 选择涂掉i行, 也可以不选，所以有n+1种选择\n",
    "            for j in range(n + 1): # 选择涂掉j列\n",
    "            # i行有i*n个方格被涂上，j列有j*n个格子被涂上，其中又有i*j个重复的格子，要减掉\n",
    "                if i * n + j * n - i * j == k:  # 看是否满足k\n",
    "                    # res += math.comb(n, i) * math.comb(n, j) # 组合数，选出i行，j列的方式\n",
    "                    res += combinationNum(n, i) * combinationNum(n, j)\n",
    "\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if k<n or k > n *n:\n",
    "            return 0\n",
    "        if k == n * n:\n",
    "            return 1\n",
    "\n",
    "        def combin(x, y):\n",
    "            a = 1\n",
    "            b = 1\n",
    "            for i in range(y):\n",
    "                a *= x-i\n",
    "                b *= y-i\n",
    "            return a//b\n",
    "\n",
    "        res = 0\n",
    "        m = k//n\n",
    "        if m*n<k:\n",
    "            m += 1\n",
    "        for im in range(m, 2*n-1):\n",
    "            x = im * n - k\n",
    "            if x == 0:\n",
    "                res += combin(n, im) * 2\n",
    "            elif im*im/4 < x:\n",
    "                break\n",
    "            else:\n",
    "                for r in range(1, im):\n",
    "                    c = im - r\n",
    "                    if c * r == x:\n",
    "                        res += combin(n, c)*combin(n, r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0,n*n):return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n,n-a,-1):\n",
    "                res*=i\n",
    "            for j in range(1,a+1):\n",
    "                res/=j\n",
    "            return res       \n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == n ** 2 or k == 0:\n",
    "            return 1\n",
    "        elif k < n:\n",
    "            return 0\n",
    "# n(i + j) - i * j = k\n",
    "# j = (k - n * i) / (n - i)\n",
    "        answer = 0\n",
    "        for row in range(n):\n",
    "            if k - n * row < 0:\n",
    "                break \n",
    "            if (k - n * row) % (n - row) == 0:\n",
    "                column = (k - n * row) // (n - row)\n",
    "                answer += math.comb(n, row) * math.comb(n, column)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "      def C(n, m):\n",
    "        if m == 0 or n == m:\n",
    "          return 1\n",
    "        return C(n - 1, m - 1) + C(n - 1, m)\n",
    "      L = 0\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          if i * n + j * n - i *j == k:\n",
    "            L += C(n, i) * C(n, j)\n",
    "      if k in (0, n * n):\n",
    "        return 1\n",
    "      return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k in (0, n*n):  # 如果 k 为 0 或者等于总单元格数，只有一种涂色方案\n",
    "            return 1\n",
    "        \n",
    "        def get(n, a):\n",
    "            # 计算组合公式的迭代版本\n",
    "            res = 1\n",
    "            for i in range(n, n - a, -1):\n",
    "                res *= i\n",
    "            for j in range(1, a + 1):\n",
    "                res /= j\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n * (i + j) - (i * j) == k:\n",
    "                    ans += get(n, i) * get(n, j)  # 计算符合条件的行列组合的方案数并累加\n",
    "        \n",
    "        return int(ans)  # 返回累计的符合条件的涂色方案数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == n**2 or k == 0: return 1\n",
    "        elif k < n: return 0\n",
    "        else:\n",
    "            comb = [math.comb(n,i) for i in range(0,n)]\n",
    "            ans = 0\n",
    "            for i in range(0,n):\n",
    "                if (k-n*i) % (n-i) == 0 and (j := (k-n*i) // (n-i)) >= 0 and j < n:\n",
    "                    ans += comb[i] * comb[j]\n",
    "            return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        #  特殊情况一定要先排除！\n",
    "        if k==n**2:\n",
    "            return 1\n",
    "        if k==0:\n",
    "            return 1\n",
    "\n",
    "\n",
    "        # 计算排列组合的函数\n",
    "        def f(c,n):\n",
    "            sub = 1\n",
    "            for i in range(1,c+1):\n",
    "                sub*=i\n",
    "            sup = 1\n",
    "            for i in range(n-c+1,n+1):\n",
    "                sup*=i\n",
    "            return sup//sub\n",
    "\n",
    "        # 暴力寻找符合条件的行列情况\n",
    "        ans = 0\n",
    "        for a in range(n+1):\n",
    "            for b in range(n+1):\n",
    "                if a*n + (b)*(n-a)==k:\n",
    "                    #  注意行列不同的情况数是相乘！\n",
    "                    ans+= f(a,n)*f(b,n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        #如果k=0或者k=n*n\n",
    "        if k in (0,n*n):\n",
    "            return 1\n",
    "        def get(n,a):\n",
    "            #计算组合公式递归版\n",
    "            def helper(n):\n",
    "                if n<=1:return 1\n",
    "                return  n*helper(n-1)\n",
    "            return helper(n)/(helper(a)*helper(n-a))        \n",
    "        ans=0\n",
    "        #满足条件的状况，利用总的-重复的\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if n*(i+j)-(i*j) ==k:\n",
    "                    ans+=get(n,i)*get(n,j)             \n",
    "        return int(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb  # 组合函数\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1  # 全部都是白色\n",
    "        if k == n * n:\n",
    "            return 1  # 全部都是黑色\n",
    "        total_ways = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                black_cells = i * n + j * n - i * j\n",
    "                if black_cells == k:\n",
    "                    total_ways += comb(n, i) * comb(n, j)\n",
    "        return total_ways\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.paintingPlan(2, 2))  # 输出应该是 4\n",
    "print(sol.paintingPlan(2, 4))  # 输出应该是 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == n * n:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if n * (i + j) - i * j == k:\n",
    "                    ans += comb(n, i) * comb(n, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        if k == 0: return 1\n",
    "        if k < n: return 0\n",
    "        if k == n ** 2: return 1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def A(a, b):\n",
    "            res = 1\n",
    "            for i in range(n,n-a, -1):\n",
    "                res *= i\n",
    "                # print(res)\n",
    "            if res == 0: return 1\n",
    "            for i in range(1, a + 1):\n",
    "                res /= i\n",
    "            return res\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if n * (i + j) - i * j == k:\n",
    "                    res += A(i, n) * A(j, n)\n",
    "                    # print(res)\n",
    "        return int(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintingPlan(self, n: int, k: int) -> int:\n",
    "        def combinationNum(n,a): #计算组合数公式迭代版\n",
    "            res = 1\n",
    "            for i in range(n, n - a, -1):\n",
    "                res *= i\n",
    "            for j in range(1, a + 1):\n",
    "                res /= j\n",
    "            return res\n",
    "\n",
    "        if k == 0 or k == n * n:\n",
    "            return 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n + 1): # 选择涂掉i行, 也可以不选，所以有n+1种选择\n",
    "            for j in range(n + 1): # 选择涂掉j列\n",
    "            # i行有i*n个方格被涂上，j列有j*n个格子被涂上，其中又有i*j个重复的格子，要减掉\n",
    "                if i * n + j * n - i * j == k:  # 看是否满足k\n",
    "                    res += math.comb(n, i) * math.comb(n, j) # 组合数，选出i行，j列的方式\n",
    "                    # res += combinationNum(n, i) * combinationNum(n, j)\n",
    "\n",
    "        return res \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
